
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1880. -- [Sdoi2009]Elaxia的路线 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1880: [Sdoi2009]Elaxia的路线</h2><span class=green>Time Limit: </span>4 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>184&nbsp;&nbsp;<span class=green>Solved: </span>80<br>[<a href='submitpage.php?id=1880'>Submit</a>][<a href='problemstatus.php?id=1880'>Status</a>][<a href='bbs.php?id=1880'>Discuss</a>]</center><h2>Description</h2><div class=content>最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们
必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们
希望在节约时间的前提下，一起走的时间尽可能的长。
现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路
口，M条路，经过每条路都需要一定的时间。
具体地说，就是要求无向图中，两对点间最短路的最长公共路径。</div><h2>Input</h2><div class=content>第一行：两个整数N和M（含义如题目描述）。
第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤
≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别
x1,y1和x2,y2）。
接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表
u和v之间有一条路，经过这条路所需要的时间为l。
出出出格格格式式式：：：
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。</div><h2>Output</h2><div class=content>一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>9 10<br />
1 6 7 8<br />
1 2 1<br />
2 5 2<br />
2 3 3<br />
3 4 2<br />
3 9 5<br />
4 5 3<br />
4 6 4<br />
4 7 2<br />
5 8 1<br />
7 9 1<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>3</span></div><h2>HINT</h2>
			<div class=content><p>对于30%的数据，N ≤ 100；<br />
对于60%的数据，N ≤ 1000；<br />
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day2'>Day2</a></p></div><center>[<a href='submitpage.php?id=1880'>Submit</a>][<a href='problemstatus.php?id=1880'>Status</a>][<a href='bbs.php?id=1880'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
